package first.forHuaWei.动态规划;

/**
 * @ClassName LC10
 * @description:
 * @author: 荣燊
 * @create: 2021-09-09 20:38
 **/
public class LC10 {
    // 正则表达式的匹配
    public static void main(String[] args) {

    }

    /**
     * 1.如果第i位与第j位都是小写字母，或者第j位是。
     * 2.如果第j位是*，那么就需要思考两种情况：
     *      1.s[i]=p[j−1]表示，查看前一位的匹配情况，
     *      2.s[i]/=p[j−1]，不匹配，将第j-1位丢掉，也就是匹配0次，dp[i][j-2]
     */
    public static boolean isMatch(String s, String p) {
        // dp[i][j]表示字符串s的第i位之前 和 p第j位之前的 字符是否匹配
        int len1 = s.length();
        int len2 = p.length();
        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[0][0] = true;
        // 开始匹配
        for (int i=0; i<=len1; i++) {
            for (int j=1; j<=len2; j++) {
                if (p.charAt(j-1) == '*') { //p的第j位是*号
                    dp[i][j] = dp[i][j-2]; //匹配0次，将匹配的两字符丢弃
                    if (matches(s, p, i, j-1)) { // 第j-1位字符不是*
                        //那么可以将第i抛弃，继续匹配
                        dp[i][j] = dp[i][j] || dp[i-1][j];
                    }
                } else { // p的第j位置是小数点和字母的情况
                    // 匹配
                    if (matches(s, p, i, j)) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
        }
        return dp[len1][len2];
    }

    public static boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}
